package org.labuladong.滑动窗口;

import java.util.HashMap;
import java.util.Map;

/**
 * @Auther: qingle
 * @Date: 2024/10/25-0:47
 * @Description:
 * 给你⼀个字符串 s 、⼀个字符串 t，返回 s 中涵盖 t 所有字符的最⼩⼦串；如果 s 中不存在涵盖 t 所有字符
 * 的⼦串，则返回空字符串 ""。
 *
 * 标签：滑动窗⼝，数组双指针
 * @version: 1.0
 */
public class LC76_最小覆盖子串_answer {

	/* 滑动窗⼝算法框架 */
		public String minWindow(String s, String t) {
			// 使用HashMap存储t中所有字符及其出现次数
			Map<Character, Integer> need = new HashMap<>();
			for (char c : t.toCharArray()) {
				need.put(c, need.getOrDefault(c, 0) + 1);
			}

			int left = 0, right = 0;
			int valid = 0; // 记录窗口中满足条件的字符数量
			Map<Character, Integer> window = new HashMap<>();

			// 记录最小覆盖子串的起始索引及长度
			int start = 0, len = Integer.MAX_VALUE;

			while (right < s.length()) {
				// c 是将移入窗口的字符
				char c = s.charAt(right);
				right++;

				// 进行窗口内数据的一系列更新
				if (need.containsKey(c)) {
					window.put(c, window.getOrDefault(c, 0) + 1);
					if (window.get(c).equals(need.get(c))) {
						valid++;
					}
				}

				// 判断左侧窗口是否要收缩
				while (valid == need.size()) {
					// 在这里更新最小覆盖子串
					if (right - left < len) {
						start = left;
						len = right - left;
					}

					// d 是将移出窗口的字符
					char d = s.charAt(left);
					left++;

					// 进行窗口内数据的一系列更新
					if (need.containsKey(d)) {
						if (window.get(d).equals(need.get(d))) {
							valid--;
						}
						window.put(d, window.get(d) - 1);
					}
				}
			}

			// 返回最小覆盖子串
			return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
		}

		public static void main(String[] args) {
			LC76_最小覆盖子串_answer solution = new LC76_最小覆盖子串_answer();
			String s = "ADOBECODEBANC";
			String t = "ABC";
			System.out.println("Minimum window substring: " + solution.minWindow(s, t)); // 应输出 "BANC"
		}
	}
